package com.practice.recursive;

import java.util.Stack;


public class Catalan2 {
	public void generate(int count) {
		print(count, count, new char[2*count], 0);
	}
	
	public void print(int l, int r, char[] str, int count) {
		if (l==0 && r==0) print(str);
		if (l>0) {
			str[count] = 'X';
			print(l-1, r, str, count+1);
		}
		if (r>l) {
			str[count] = 'Y';
			print(l, r-1, str, count+1);
		}
	}
	
	private void print(char[] str) {
		Stack<String> s = new Stack<String>();
		int k = 0;
		
		s.push(getChar(k++));
		for (int i=0; i<str.length; i++) {
			if (str[i] == 'X') {
				s.push(getChar(k++));
			}
			else {
				String t = s.pop();
				s.push("(" + s.pop() + t + ")");
			}
		}
		
		System.out.println(s.pop());
	}
	
	private String getChar(int k) {
		char c = (char) ('A' + k);
		return c + "";
	}
}
